/*
 * @lc app=leetcode.cn id=416 lang=java
 *
 * [416] 分割等和子集
 */

// @lc code=start
class Solution {
    public boolean canPartition(int[] nums) {
        if(nums.length==1)return false;
        int sum=0;
        for(Integer i:nums){
            sum+=i;
        }
        if(sum%2!=0)return false; 
        int target=sum/2;
        int[] dp=new int[10001];//200*100/2+1=10001
        dp[0]=0;
        for(int i=0;i<nums.length;i++){
            for(int j=target;j>=nums[i];j--){//dp[j]表示背包容量为j时放物品的最大价值(这里价值和重量一样了)
                dp[j]=Math.max(dp[j], dp[j-nums[i]]+nums[i]);
            }
        }
        //因为实际需求就是背包大小为target能不能放满，也就是dp[target]最大是否能放target价值的物品
        if(dp[target]==target){
            return true;
        }else{
            return false;
        }
    }

    
}
// @lc code=end

